//https://leetcode.cn/problems/longest-increasing-subsequence/submissions/578842580/
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // int n=nums.size();
        // vector<int> dp(n,1);
        // for(int i=1;i<n;++i)
        // {
        //         for(int j=i;j>=0;--j)
        //         {
        //             if(nums[i]>nums[j])dp[i]=max(dp[i],dp[j]+1);
        //         }
        // }
        // int ret=0;
        // for(auto tmp:dp)if(ret<tmp)ret=tmp;
        // return ret;
        int n = nums.size();
        vector<int> d(n);
        d[0] = nums[0];
        int len = 0;
        for (int i = 1; i < n; ++i)
        {
            if (nums[i] > d[len])d[++len] = nums[i];
            else
            {
                int left = 0, right = len;
                while (left < right)
                {
                    int mid = left + (right - left) / 2;
                    if (d[mid] < nums[i])left = mid + 1;
                    else right = mid;
                }
                d[left] = nums[i];
            }
        }
        return len + 1;
    }
};